package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=23286&ru=%2Fexam%2Foj&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM12 单链表的排序</a>
 *
 * @author c2b
 * @since 2024/3/14 11:18
 */
public class BM12SortInList {

    public static class Solution {
        public ListNode sortInList (ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // 通过快慢指针找到中点。分别对前半段、后半段排序，然后合并两个有序链表
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode secondListNodeHead = slow.next;
            slow.next = null;
            return merge(sortInList(head), sortInList(secondListNodeHead));

        }

        private ListNode merge(ListNode list1, ListNode list2) {
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }
            ListNode dummy = new ListNode(-1);
            ListNode currNode = dummy;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    currNode.next = list1;
                    list1 = list1.next;
                } else {
                    currNode.next = list2;
                    list2 = list2.next;
                }
                currNode = currNode.next;
            }
            if (list1 != null) {
                currNode.next = list1;
            }
            if (list2 != null) {
                currNode.next = list2;
            }
            return dummy.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode head = new ListNode(1);
        head.next = new ListNode(3);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(5);
        head.next.next.next.next = new ListNode(4);

        Printer.printListNode(solution.sortInList(head));
    }
}
